package LC;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @ClassName LC637
 * @Description: TODO
 * @Author hl
 * @Date 2020/8/27
 * @Version V1.0
 **/
public class LC637 {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list=new ArrayList<>();
        if(root==null) return  list;
        Queue<TreeNode> queue1=new LinkedList<>();
        Queue<TreeNode> queue2=new LinkedList<>();
        queue1.add(root);
       while(!queue1.isEmpty()||!queue2.isEmpty()){
           if(!queue1.isEmpty()){
               int size=queue1.size();
               double sum=0;
               while(!queue1.isEmpty()){
                   TreeNode node =queue1.poll();
                   sum+=node.val;
                   if(node.left!=null){
                       queue2.add(node.left);
                   }
                   if(node.right!=null){
                       queue2.add(node.right);
                   }
               }
               list.add(sum/size);
           }else{
               int size=queue2.size();
               double sum=0;
               while(!queue2.isEmpty()){
                   TreeNode node =queue2.poll();
                   sum+=node.val;
                   if(node.left!=null){
                       queue1.add(node.left);
                   }
                   if(node.right!=null){
                       queue1.add(node.right);
                   }
               }
               list.add(sum/size);
           }
       }

    return  list;
    }
}
